/**
 * 两个列表相加
 */
public class AddTwoNode {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        int carry = 0;
        // sum Node -> next
        ListNode dummy = new ListNode(0);
        ListNode pre = dummy;
        while (l1 != null && l2 != null) {
            int total = l1.val + l2.val + carry;
            int number = total % 10;
            carry = total / 10;
            ListNode node = new ListNode(number);
            dummy.next = node;
            dummy = dummy.next;
            l1 = l1.next;
            l2 = l2.next;
        }
        while (l1 != null) {
            int total = l1.val + carry;
            int number = total % 10;
            carry = total / 10;
            ListNode node = new ListNode(number);
            dummy.next = node;
            dummy = dummy.next;
            l1 = l1.next;
        }
        while (l2 != null) {
            int total = l2.val + carry;
            int number = total % 10;
            carry = total / 10;
            ListNode node = new ListNode(number);
            dummy.next = node;
            dummy = dummy.next;
            l2 = l2.next;
        }
        if (carry != 0) {
            ListNode node = new ListNode(carry);
            dummy.next = node;
        }
        return pre.next;
    }

    public  AddNode addTwoNumbers(AddNode l1 , AddNode l2){
        if (l1 == null){
            return l2;
        }
        if (l2 == null){
            return l1;
        }
        //进位
        int carry = 0 ;
        //相加的新链表
        AddNode dummy = new AddNode(0);
        AddNode head = dummy;
        while(l1 != null && l2 !=null){
            int sum =l1.data +l2.data +carry;
            //进位
            carry = sum/10;
            //和
            int num = sum%10;
            AddNode addNode = new AddNode(num);
            dummy.next = addNode;
            dummy =addNode;
            l1=l1.next;
            l2=l2.next;
        }
        while(l1!= null){
            int sum =l1.data + carry;
            //进位
            carry = sum/10;
            //和
            int num = sum%10;
            AddNode addNode = new AddNode(num);
            dummy.next = addNode;
            dummy =addNode;
            l1=l1.next;
        }
        while (l2!=null){
            int sum =l2.data + carry;
            //进位
            carry = sum/10;
            //和
            int num = sum%10;
            AddNode addNode = new AddNode(num);
            dummy.next = addNode;
            dummy =addNode;
            l2=l2.next;
        }
        //只有进位l1,l2都遍历完成了但仍有进位
        while (carry != 0){
            AddNode addNode = new AddNode(carry);
            dummy.next = addNode;
        }
        return  head.next;
    }

    public static void main(String[] args) {
        //链表L ：1 2 5  + 链表S ：1 2 5
        AddNode addNodeL1 = new AddNode(1);
        AddNode addNodeL2 = new AddNode(2);
        AddNode addNodeL3 = new AddNode(3);
        AddNode addNodeS1 = new AddNode(1);
        AddNode addNodeS2 = new AddNode(2);
        AddNode addNodeS3 = new AddNode(3);
        addNodeL1.next= addNodeL2;
        addNodeL2.next= addNodeL3;

        addNodeS1.next= addNodeS2;
        addNodeS2.next= addNodeS3;
       /* while (addNodeL1 != null) {
            System.out.print(addNodeL1.data);
            if (addNodeL1.next != null) {
                System.out.print(" -> ");
            }
            addNodeL1 = addNodeL1.next;
        }
        System.out.println();
        while (addNodeS1 != null) {
            System.out.print(addNodeS1.data);
            if (addNodeS1.next != null) {
                System.out.print(" -> ");
            }
            addNodeS1 = addNodeS1.next;
        }
*/
        AddTwoNode m = new AddTwoNode();
        AddNode addNode = m.addTwoNumbers(addNodeL1, addNodeS1);

        while(addNode != null){

            System.out.print(addNode.data);
            if (addNode.next !=null){
                System.out.print("-->");
            }
            addNode=addNode.next;
        }
    }

}
